#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>



char lookahead;

int num;

enum TERMINAL {

	ID,

	ADD,

	MUL,

	LBR,

	RBR,

	END,

	ERR

};



enum NON_TERMINAL {

	E,

	T,

	F

};



enum ACTION_TYPE {

	SHIFT,

	REDUCE,

	ERROR,

	ACC

};



#define NUM_TERMINAL  6

#define NUM_NONTERMINAL  3

#define NUM_STATES  12



struct action{

	enum ACTION_TYPE type;

	int id;

}  actionTable[NUM_STATES][NUM_TERMINAL];



int gotoTable[NUM_STATES][NUM_NONTERMINAL];



int stackPtr;

int valPtr;

int stack[1024];

int value[1024];

void push(int state) {

	stack[stackPtr] = state;

	stackPtr ++;

}



void pop() {

	stackPtr --;

}



int top() {

	return stack[stackPtr - 1];

}



void valset(int offset, int v) {

	value[stackPtr - 1 + offset] = v;

}

int valget(int offset) {

	return value[stackPtr - 1 + offset];

}



void init() {

	int i, j;



	//stack

	stackPtr = 0;

	push(0);



	//action and goto tables

	for(i = 0; i < NUM_STATES; i ++) {

		for(j = 0; j < NUM_TERMINAL; j ++) {

		actionTable[i][j].type = ERROR;

		}

		for(j = 0; j < NUM_NONTERMINAL; j ++) {

		gotoTable[i][j] = -1;

		}

	}



	//fill in the goto table

	gotoTable[0][E] = 1;

	gotoTable[0][T] = 2;

	gotoTable[0][F] = 3;

	//... your turn

	

	gotoTable[4][E] = 8;

    	gotoTable[4][T] = 2;

    	gotoTable[4][F] = 3;

    	

    	gotoTable[6][T] = 9;

    	gotoTable[6][F] = 3;

    

    	gotoTable[7][F] = 10;





	//fill in the action table

	actionTable[2][ADD].type = REDUCE;

	actionTable[2][ADD].id = 2;

	actionTable[2][MUL].type = SHIFT;

	actionTable[2][MUL].id = 7;

	actionTable[2][RBR].type = REDUCE;

	actionTable[2][RBR].id = 2;

	actionTable[2][END].type = REDUCE;

	actionTable[2][END].id = 2;

	//... your turn

    

    	actionTable[3][ADD].type = REDUCE;

    	actionTable[3][ADD].id = 4;

	actionTable[3][MUL].type = REDUCE;

	actionTable[3][MUL].id = 4;

	actionTable[3][RBR].type = REDUCE;

	actionTable[3][RBR].id = 4;

	actionTable[3][END].type = REDUCE;

	actionTable[3][END].id = 4;

    

    	actionTable[4][ID].type = SHIFT;

    	actionTable[4][ID].id = 5;

    	actionTable[4][LBR].type = SHIFT;

    	actionTable[4][LBR].id = 4;

    	

    	actionTable[5][ADD].type = REDUCE;

    	actionTable[5][ADD].id = 6;

	actionTable[5][MUL].type = REDUCE;

	actionTable[5][MUL].id = 6;

	actionTable[5][RBR].type = REDUCE;

	actionTable[5][RBR].id = 6;

	actionTable[5][END].type = REDUCE;

	actionTable[5][END].id = 6;

    

    	actionTable[6][ID].type = SHIFT;

    	actionTable[6][ID].id = 5;

    	actionTable[6][LBR].type = SHIFT;

    	actionTable[6][LBR].id = 4;

    

    	actionTable[7][ID].type = SHIFT;

    	actionTable[7][ID].id = 5;

    	actionTable[7][LBR].type = SHIFT;

    	actionTable[7][LBR].id = 4;

    

    	actionTable[8][ADD].type = SHIFT;

    	actionTable[8][ADD].id = 6;

    	actionTable[8][RBR].type = SHIFT;

    	actionTable[8][RBR].id = 11;

    

    	actionTable[9][ADD].type = REDUCE;

    	actionTable[9][ADD].id = 1;

	actionTable[9][MUL].type = SHIFT;

	actionTable[9][MUL].id = 7;

	actionTable[9][RBR].type = REDUCE;

	actionTable[9][RBR].id = 1;

	actionTable[9][END].type = REDUCE;

	actionTable[9][END].id = 1;

    

    	actionTable[10][ADD].type = REDUCE;

    	actionTable[10][ADD].id = 3;

	actionTable[10][MUL].type = REDUCE;

	actionTable[10][MUL].id = 3;

	actionTable[10][RBR].type = REDUCE;

	actionTable[10][RBR].id = 3;

	actionTable[10][END].type = REDUCE;

	actionTable[10][END].id = 3;

    

    	actionTable[11][ADD].type = REDUCE;

    	actionTable[11][ADD].id = 5;

	actionTable[11][MUL].type = REDUCE;

	actionTable[11][MUL].id = 5;

	actionTable[11][RBR].type = REDUCE;

	actionTable[11][RBR].id = 5;

	actionTable[11][END].type = REDUCE;

	actionTable[11][END].id = 5;

    

    	actionTable[0][ID].type = SHIFT;

    	actionTable[0][ID].id = 5;

    	actionTable[0][LBR].type = SHIFT;

    	actionTable[0][LBR].id = 4;

    

    	actionTable[1][ADD].type = SHIFT;

    	actionTable[1][ADD].id = 6;

    	actionTable[1][END].type = ACC;

    	actionTable[1][END].id = 0;

}



enum TERMINAL lexical(FILE *fp) {



	lookahead = getc(fp);



	while(lookahead == ' ' || lookahead == '\t' || lookahead == '\n') {

		lookahead = getc(fp);

	}



	if(isdigit(lookahead)) {

		num = 0;

		do {

			num = num * 10 + lookahead - '0';

			lookahead = getc(fp);

		} while(isdigit(lookahead)); 

		ungetc(lookahead, fp);

		return ID;

	} else if (lookahead == '+') {

		return ADD;

	} else if (lookahead == '*') {

		return MUL;

	} else if(lookahead == EOF) {

		return END;

	}else if(lookahead == '(') {

		return LBR;

	} else if(lookahead == ')') {

		return RBR;

	} else {

		return ERR;

	}

}



void parse(enum TERMINAL *input, int *number) {

	int currentState = 0;

	int currentValue = 0;

	int index = 0;



	while(1) {

		printf("currentState: %d\n", currentState);

		switch(actionTable[currentState][input[index]].type) {

			case SHIFT:

				currentValue = number[index];//store the current shifted value for further use

				//how to shift

                		

				push(actionTable[currentState][input[index]].id);

				valset(0,currentValue);

                		currentState=top();

                		index++;

				break;

			case REDUCE:

				switch(actionTable[currentState][input[index]].id) {

					case 1:

						//reduce by production 1

						

                        			pop();

                        			pop();

                        			pop();

                        			push(gotoTable[top()][E]);

						valset(0,valget(0)+valget(2));

                        			currentState=top();

						break;

					case 2:

						//reduce by production 2

                        			pop();

                        			push(gotoTable[top()][E]);

                        			currentState=top();

						break;

					case 3:

						//reduce by production 3

                        			

                        			pop();

                        			pop();

                        			pop();

                        			push(gotoTable[top()][T]);

						valset(0,valget(0)*valget(2));

                        			currentState=top();

						break;

					case 4:

						//reduce by production 4

                    				pop();

                                                push(gotoTable[top()][T]);

                                                currentState=top();

						break;

					case 5:

						//reduce by production 5

                    				pop();

                                                pop();

                                                pop();

                                                push(gotoTable[top()][F]);

						valset(0,valget(1));

                                                currentState=top();

						break;

					case 6:

						//reduce by production 6

                    				pop();

                                                push(gotoTable[top()][F]);

                                                currentState=top();

						break;

					default:

						printf("ERROR REDUCE\n");

						exit(-1);

						break;

				}

				break;

			case ERROR:

				printf("ERROR ACTION\n");

				exit(-1);

				break;

			case ACC:

				if(input[index] == END) {

					printf("ACC\n");

					printf("%d\n",value[1]);

					return;

				} else {

					printf("ERROR ACC\n");

					exit(-1);

				}

				break;

		}

	}

//printf("%d\n",valget(0));

}





int main(int argc, char **argv) {

	enum TERMINAL input[1024]; 

	int number[1024];

	int inputIndex = 0;

	FILE *fp;

	enum TERMINAL temp;

	if(argc < 2) {

		printf("insufficient arguments");

		return 1;

	}

	fp = fopen(argv[1], "r");

	while((temp = lexical(fp)) != END) {

		input[inputIndex] = temp;

		number[inputIndex] = (temp == ID ? num : -1);

		inputIndex ++;

	}



	input[inputIndex] = END;

	fclose(fp);



	init();

	parse(input, number);

//printf("%d\n",valget(-2));



	return 0;

}

